package com.agile.leetcode.middle.robot;

import java.util.HashSet;
import java.util.Set;

/**
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * <p>
 * 示例 2：
 * <p>
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author KD
 * @Date 2021/2/2 9:48
 */
public class Robot {
    public static void main(String[] args) {
        Robot robot = new Robot();
        int i = robot.movingCount(3, 2, 17);
        int i1 = robot.movingCount_1(3, 2, 17);
        System.out.println(i);
        System.out.println(i1);


    }

    public int movingCount(int m, int n, int k) {
        // 创建图
        int[][] map = new int[m][n];
        // 将不能走的点标出
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                // 判断是否通过
                boolean through = through(i, j, k);
                // 没通过
                if (!through) {
                    map[i][j] = 1;
                }
            }
        }
        // 看能否出去
        Set<String> set = new HashSet<>();
        // 到顶点
        swap(map, 0, 0, m, n, set);
        return set.size();
    }

    public boolean swap(int[][] map, int i, int j, int m, int n, Set<String> set) {
        if (map[m - 1][n - 1] == 2) {
            set.add((m - 1) + "=" + (n - 1));
            return true;
        } else {
            if (i >= 0 && i < m && j >= 0 && j < n && map[i][j] == 0) {
                set.add(i + "=" + j);
                System.out.println(i + "=" + j);
                map[i][j] = 2;
                // 向下走
                if (swap(map, i + 1, j, m, n, set)) {
                    return true;
                } else if (swap(map, i, j + 1, m, n, set)) {
                    return true;
                } else if (swap(map, i - 1, j, m, n, set)) {
                    return true;
                } else if (swap(map, i, j - 1, m, n, set)) {
                    return true;
                } else {
                    map[i][j] = 3;
                }
            } else {
                return false;
            }
        }
        return false;
    }

    public boolean through(int x, int y, int k) {
        // 求和
        if (getSum(x) + getSum(y) > k) return false;
        return true;
    }

    public int getSum(int n) {
        // 定义和
        int sum = 0;
        do {
            // 取余数
            int mod = n % 10;
            sum += mod;
            n = n / 10;
        } while (n != 0);
        // 返回值
        return sum;
    }

    public int movingCount_1(int m, int n, int k) {
        // 创建访问数组
        boolean[][] isVisited = new boolean[m][n];
        return dfs(m, n, k, 0, 0, isVisited);
    }

    /**
     * leetcod解法
     *
     * @param m
     * @param n
     * @param k
     * @param i
     * @param j
     * @param isVisited
     * @return
     */
    public int dfs(int m, int n, int k, int i, int j, boolean[][] isVisited) {
        // 退出条件
        if ((getSum(i) + getSum(j)) > k || i < 0 || i >= m || j < 0 || j >= n || isVisited[i][j]) {
            return 0;
        }
        // 标记已访问
        isVisited[i][j] = true;
        // 递归
        return 1 + dfs(m, n, k, i + 1, j, isVisited)
                + dfs(m, n, k, i, j + 1, isVisited)
                + dfs(m, n, k, i - 1, j, isVisited)
                + dfs(m, n, k, i, j - 1, isVisited);
    }
}
